package oj.hot100;

import java.util.List;

public class 单词拆分 {
    public boolean wordBreak(String ss, List<String> wordDict) {
        ss = ' '+ss;
        char[] s = ss.toCharArray();
        int n = s.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for(int i = 1;i < n;i++) {
            for(int j = i;j >= 1;j--) {
                if(dp[j-1] == true && wordDict.contains(ss.substring(j,i+1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n-1];
    }
}
